package Algorithm;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 2021.8.31
 *
 * @author 23737
 */
class main {
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 4, 5, 6, 7, 8, 1};
        int[] array1 = new int[]{2, 3, 4, 5, 6, 7, 8, 1};
        //钟摆排序的测试
        GuLu s = new GuLu();
        s.GuLuSort(array);
        System.out.println("冒泡排序的优化： ");
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();
        s.GuLuSort2(array1);
        System.out.println("冒泡排序的原始版本： ");
        for (int i : array1) {
            System.out.print(i + " ");
        }
        System.out.println();

        //快排非递归方法的实现测试
//        new FasterSort().quickSortNoRecursion(array, 0, array.length - 1);

        new HeapSort().headSort(array);
        System.out.println(Arrays.toString(array));
    }
}


class GuLu {
    //鸡尾酒排序（钟摆排序）

    /**
     * 其内部原理和冒泡排序的方式相似，但是在时空复杂度上进行了优化
     */
    public void GuLuSort(int array[]) {
        int temp = 0;
        for (int i = 0; i < array.length / 2; i++) {
            //有序标记，每一轮的初始值都是true
            boolean isSorted = true;
            //奇数轮，从左往右进行比较和交换
            for (int j = 0; j < array.length - 1; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    //有元素进行了交换，所以不是有序的，标记为false
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
            //在偶数轮之前，将isSorted重新进行标记，标记为true
            isSorted = true;
            //偶数轮，从右向左进行比较和交换
            for (int j = array.length - i - 1; j > i; j--) {
                if (array[j] < array[j - 1]) {
                    temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                    //有元素进行了交换，所以不是有序的，标记为false
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
        }
    }

    //冒泡排序的原始版本
    public void GuLuSort2(int array[]) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

}


//快排

/**
 * 每一轮都会挑选一个基准元素，并让其他比他大的元素移动到基准元素的一边，比他小的移动到另外一端
 */
class FasterSort {

    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 4, 5, 6, 7, 8, 1};
        new FasterSort().quickSort(array, 0, array.length - 1);
        System.out.println("快排（递归下）的排序： ");
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

    public void quickSort(int array[], int startIndex, int endIndex) {
        //递归结束的条件：startIndex大于或者等于endIndex时
        if (startIndex >= endIndex) {
            return;
        }
        //得到基准元素
//        int pivotIndex = partition(array,startIndex,endIndex);
        int pivotIndex = partitionSingle(array, startIndex, endIndex);
        //根据基准元素，分成两部分来进行递归排序
        quickSort(array, startIndex, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, endIndex);
    }

    /**
     * 分治（双边循环法）
     *
     * @param arr        待交换的数组
     * @param startIndex 起始下标
     * @param endIndex   结束下标
     */
    private int partition(int[] arr, int startIndex, int endIndex) {
        //取第一个位置（也可以随机选择位置）的元素来作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            //控制right指针比较并进行左移
            while (left < right && arr[right] > pivot) {
                right--;
            }
            //控制left指针比较并右移
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //交换left和right指针所指向的元素
            if (left < right) {
                int p = arr[left];
                arr[left] = arr[right];
                arr[right] = p;
            }
        }

        //pivot和指针重合点交换
        arr[startIndex] = arr[left];
        arr[left] = pivot;

        return left;
    }


    /**
     * 分治（单边循环法）
     *
     * @param arr        待交换的数组
     * @param startIndex 起始下标
     * @param endIndex   结束下标
     */
    private int partitionSingle(int[] arr, int startIndex, int endIndex) {
        //取第一个位置（也可以随机选择位置）的元素来作为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;

        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot) {
                mark++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }

        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }


    //使用非递归的方法来实现快排
    public void quickSortNoRecursion(int[] arr, int startIndex, int endIndex) {
        //用一个集合栈来代替递归的函数栈
        Stack<Map<String, Integer>> quickSortStack = new Stack<>();
        //整个队列的起止下标，以哈希的形式入栈
        Map rootParam = new HashMap();
        rootParam.put("startIndex", startIndex);
        rootParam.put("endIndex", endIndex);
        quickSortStack.push(rootParam);

        //循环结束条件：栈为空时
        while (!quickSortStack.isEmpty()) {
            //栈顶元素出栈，得到起止下标
            Map<String, Integer> param = quickSortStack.pop();
            //得到基准位置的元素
            int pivotIndex = partitionSingle(arr, param.get("startIndex"), param.get("endIndex"));

            //根据基准元素分成两部分，把每一部分的起止下标入栈
            if (param.get("startIndex") < pivotIndex - 1) {
                HashMap<String, Integer> leftParam = new HashMap<>();
                leftParam.put("startIndex", param.get("startIndex"));
                leftParam.put("endIndex", pivotIndex - 1);
                quickSortStack.push(leftParam);
            }
            if (pivotIndex + 1 < param.get("endIndex")) {
                HashMap<String, Integer> rightParam = new HashMap<>();
                rightParam.put("startIndex", pivotIndex + 1);
                rightParam.put("endIndex", param.get("endIndex"));
                quickSortStack.push(rightParam);
            }
        }
    }
}

class HeapSort {
    /**
     * 下沉 调整
     *
     * @param arr         待调整的堆
     * @param parenrIndex 要下沉的父节点
     * @param length      堆的有效大小
     */
    public void downAdjust(int[] arr, int parenrIndex, int length) {
        //temp来保存父节点值，用于最后的赋值
        int temp = arr[parenrIndex];
        int childIndex = 2 * parenrIndex + 1;
        while (childIndex < length) {
            //如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
            if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
                childIndex++;
            }
            //如果父节点大于任何一个孩子的值，则直接跳出
            if (temp >= arr[childIndex]) {
                break;
            }
            //无须真正进行交换，单向赋值即可
            arr[parenrIndex] = arr[childIndex];
            parenrIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        arr[parenrIndex] = temp;
    }

    /**
     * 堆排序（升序）
     *
     * @param arr 待调整的堆
     */
    public void headSort(int[] arr) {
        // 1.把无序数组构建成最大堆
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            downAdjust(arr, i, arr.length);
        }
        System.out.println(Arrays.toString(arr));
        // 2.循环删除堆顶元素，移到集合尾部，调整堆产生新的堆顶
        for (int i = arr.length - 1; i > 0; i--) {
            //最后一个元素和第一个元素进行交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            //下沉调整最大堆
            downAdjust(arr, 0, i);
        }
    }
}

//对所有排序算法的总结
class Conclusion {

    public static void main(String[] args) {

    }

    //冒泡排序
    public static void BubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    //选择排序
    public static void select_sort(int array[], int lenth) {
        for (int i = 0; i < lenth - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < lenth; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }

    //插入排序
    public static void insert_sort(int array[], int lenth) {
        int temp;
        for (int i = 0; i < lenth - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (array[j] < array[j - 1]) {
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                } else {         //不需要交换
                    break;
                }
            }
        }
    }

    //希尔排序
    public static void shell_sort(int array[], int lenth) {
        int temp = 0;
        int incre = lenth;
        while (true) {
            incre = incre / 2;
            for (int k = 0; k < incre; k++) {    //根据增量分为若干子序列
                for (int i = k + incre; i < lenth; i += incre) {
                    for (int j = i; j > k; j -= incre) {
                        if (array[j] < array[j - incre]) {
                            temp = array[j - incre];
                            array[j - incre] = array[j];
                            array[j] = temp;
                        } else {
                            break;
                        }
                    }
                }
            }
            if (incre == 1) {
                break;
            }
        }
    }

    //归并排序
    public static void sort(int[] arr) {
        int[] temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr, 0, arr.length - 1, temp);
    }

    private static void sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(arr, left, mid, temp);//左边归并排序，使得左子序列有序
            sort(arr, mid + 1, right, temp);//右边归并排序，使得右子序列有序
            merge(arr, left, mid, right, temp);//将两个有序子数组合并操作
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;//左序列指针
        int j = mid + 1;//右序列指针
        int t = 0;//临时数组指针
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid) {//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while (j <= right) {//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }

}



